#!/usr/bin/env python
# interval.py
"""
Licensed under the MIT License

The interval module implements two basic forms of interval.
The simple interval (Interval) is a basic building block that can be used to easily check intervals without unions
The multiple joined intervals (MultiInterval) is a more advanced tool allowing for unions, and manipulating those unions.

The sense of 'interval' used here is in the calculus sense. 
Using regular alphanumeric characters, here are some examples:
(1, 20] -- This contains all numbers x where 1 < x <=20
[1, 1] -- This contains all numbers x where 1 <= x <= 1 -- in other words, x == 1
[2, 50] U (60, 200] -- This contains all numbers x where 2 <= x <= 50 OR 60 < x <= 200
[0, 1) U (1, 2] -- This contains all numbers x where 0 <= x < 1 OR 1 < x <= 2 -- in other words, all numbers between and including 0 and 2 EXCEPT for 1

The interval module also implements arithmetical versions of those intervals. The explanation is much more complicated, 
so please see a relevant website or book on the subject.
"""

import itertools
import operator
import re

def _grouper(n, iterable, padvalue=None):
    "grouper(3, 'abcdefg', 'x') --> ('a','b','c'), ('d','e','f'), ('g','x','x')"
    return itertools.izip(*[itertools.chain(iterable, itertools.repeat(padvalue, n-1))]*n)

def enumerate(iterable, start=0):
    return itertools.izip(itertools.count(start), iterable)

def _compare_left_endpoint(interval1, interval2):
    """Helper function for the purposes of sorting. Compare the left endpoint
    of two intervals. A closed endpoint is considered 'further left' than an
    open endpoint of the same value, for our purposes."""
         
    if (interval1.start == interval2.start):
        if (interval1.inclusive_start == interval2.inclusive_start):
            return 0
        elif interval1.inclusive_start:
            return -1
        else:
            return 1
    
    # Can't just subtract them since an infinite endpoint could mess things up
    if interval1.start < interval2.start:
        return -1
    else:
        return 1
    
def _compare_right_endpoint(interval1, interval2):
    """Helper function. Compare the right endpoint
    of two intervals. Return -1 if interval2's endpoint is further right, 1 if 
    interval1's endpoint is further right, and 0 if they're equal. A closed 
    endpoint is considered 'further right' than an
    open endpoint of the same value, for our purposes."""
         
    if (interval1.end == interval2.end):
        if (interval1.inclusive_end == interval2.inclusive_end):
            return 0
        elif interval1.inclusive_end:
            return 1
        else:
            return -1
    
    # Can't just subtract them since an infinite endpoint could mess things up
    if interval1.end < interval2.end:
        return -1
    else:
        return 1   

class Interval(object):
    """An Interval is a basic continous interval between (and inclusive or exclusive of) two points.
    It has three ways to construct it: from a unicode string representing a continuous interval, from another instance, and
    from arguments of the start and end points, and whether they are included in the interval.
    
    
    The format of the unicode string is a simple one, shown at the top. There are two numbers, the start and end points,
    separated by a comma. There are also two brackets enclosing them, representing whether each end is enclusive or exclusive.
    Example:
    >>> Interval(u'[0, 20)')
    Interval(u'[0.0, 20.0)')
    
    
    The following is how to create a new Interval from an old one-- it needs no other explanation.
    Example:
    >>> foo = Interval(u'[1,2]')
    >>> bar = Interval(foo)
    >>> foo is bar
    False
    >>> foo
    Interval(u'[1.0, 2.0]')
    >>> bar
    Interval(u'[1.0, 2.0]')
    
    
    Finally, to create a new Interval from the values of interest alone, you can use the arguments of, in order:
    start_point, end_point, whether_to_include_start, whether_to_include_end
    Example:
    >>> Interval(0.0, 5.0, True, False)
    Interval(u'[0.0, 5.0)')
    
    
    The single most important use of Interval is to check if a number is in a range.
    Example:
    >>> 1 in Interval(u'[0, 2)')
    True
    """
    
    def __init__(self, *args):
        """Initialize Interval using one of three methods: _from_string(), _from_instance(), and _from_values().
        accepts either a single Interval, a single string representing an interval without any unions, or four values:
        start, end, whether_the_start_is_inclusive, whether_the_end_is_inclusive"""
        if len(args) == 1:
            if isinstance(args[0], Interval):
                self._from_instance(*args)
            else:
                self._from_string(*args)
        elif len(args) == 4:
            self._from_values(*args)
        else:
            raise TypeError('%s takes 1 or 4 arguments (%s given)' % (type(self).__name__, len(args)))
    
    def _from_string(self, interval_repr):
        """Takes a unicode string representing a mathematical interval, and uses it to initialize the Interval"""
        assert re.compile('[[(]([0-9]+|inf?|-inf?), *([0-9]+|inf?|-inf?)[)\]]').match(interval_repr), 'Invalid formatting'
        
        representation = ''.join(unicode(interval_repr).split())
        
        start_bracket, end_bracket = representation[0], representation[-1]
        inclusive_table = {'(': False, ')': False, '[': True, ']':True}
        # FIXME: Must catch error when occurs, it's ugly/unsemantic. Raise something more appropriate.
        inclusive_start, inclusive_end = inclusive_table[start_bracket], inclusive_table[end_bracket]
        
        startstr, endstr = representation[1:-1].split(',') # FIXME: can error here, may be confusing-- should I catch it?
        start, end = float(startstr), float(endstr) # TODO: Add infinity explicitly? I must handle the inf case, as it can be gotten using this.
        
        self._from_values(start, end, inclusive_start, inclusive_end)
        
    def _from_instance(self, instance):
        """Initializes a shallow copy of the instance, holding all the same core attributes in a new instance"""
        self.start = instance.start
        self.end = instance.end
        self.inclusive_start = instance.inclusive_start
        self.inclusive_end = instance.inclusive_end
        
        self.l_cmp = instance.l_cmp
        self.r_cmp = instance.r_cmp
    
    def _from_values(self, start, end, inclusive_start, inclusive_end):
        """Programattically create a new instance given relevant values"""
        if start > end or (start == end and (not inclusive_start or not inclusive_end)):
            self._empty_interval_init()
            return None
        
        self.start = start
        self.end = end
        self.inclusive_start = inclusive_start
        self.inclusive_end = inclusive_end
        
        # It's not exactly clear, but nor is it hard to understand. read help(cmp)
        # to find what cmp() return values mean, and note that I use a cmp() in self.x_cmp when appropriate.
        if inclusive_start:
            self.l_cmp = (-1, 0)
        else:
            self.l_cmp = (-1,)
        
        if inclusive_end:
            self.r_cmp = (-1, 0)
        else:
            self.r_cmp = (-1,)
            
    def _empty_interval_init(self):
        """Make this Interval the empty interval."""
        # I'd like to be able to set these so that they work nicely with the existing methods, and
        # we don't have to call is_empty() for everything and treat empty intervals as special cases.
        # I can't think of any intuitive way to do this though. 
        self.start = None
        self.end = None
        # The values chosen for the following assignments don't really say anything about the interval, and
        # their assignment is either arbitrary, or to make certain methods work more easily.
        self.inclusive_start = False
        self.inclusive_end = False
        self.l_cmp = ()
        self.r_cmp = ()
        
    def is_empty(self):
        """Return whether this is the empty interval"""
        return self.start == None
    
    def is_degenerate(self):
        """Return whether this is a degenerate interval - i.e. one where the left endpoint and right endpoint
        are equal and both closed"""
        return self.start == self.end and self.inclusive_start and self.inclusive_end
    
    def size(self):
        """Returns the size of the Interval."""
        # while using __len__ would be all well and good, len(), and therefore __len__(), is for integer lengths.
        # This is by no means guaranteed to return an integer.
        if self.is_empty():
            return 0
        return self.end - self.start
    
    def __contains__(self, num):
        """Returns True if `num` is inside the interval, False otherwise."""
        if isinstance(num, Interval):
            if num.is_empty():
                return True # Is this a contentious assertion?
            if self.is_empty():
                return False
            return _compare_left_endpoint(self, num) <= 0 and _compare_right_endpoint(self, num) >= 0        
        
        return (cmp(self.start, num) in self.l_cmp) and (cmp(num, self.end) in self.r_cmp)
    
    # There are just so many ways you can compare intervals, and I don't want to choose any over another.
    #def __cmp__(self, otherobj): NONONO
    
    def __eq__(self, interval):
        return (self.start == interval.start and self.end == interval.end and
                self.inclusive_start == interval.inclusive_start and 
                self.inclusive_end == interval.inclusive_end)
    
    def plain_repr(self):
        if self.is_empty():
            return u"{}"
        if self.is_degenerate():
            return u"[%s]" % self.start
        if self.inclusive_start:
            lbracket = u'['
        else:
            lbracket = u'('
        if self.inclusive_end:
            rbracket = u']'
        else:
            rbracket = u')'
        
        return u"%s%s, %s%s" % (lbracket, self.start, self.end, rbracket)
        
    
    def __repr__(self):
        """Return a str representation of the object."""
        return '%s(%s)' % (type(self).__name__, repr(unicode(self)))
    
    def __unicode__(self):
        """Return a unicode representation of the object."""
        if self.is_empty():
            return u"{}"
        if self.is_degenerate():
            return u"[%s]" % self.start
        if self.inclusive_start:
            lbracket = u'['
        else:
            lbracket = u'('
        if self.inclusive_end:
            rbracket = u']'
        else:
            rbracket = u')'
        
        return u"%s%s, %s%s" % (lbracket, self.start, self.end, rbracket)
    
    def __and__(self, other):
        """Conjunction plays nicely with normal Intervals, since as long as it takes two normal Intervals, it will always return one or nothing. Unlike disjunction, we don't have to worry about MultiIntervals. We may wish to specifically define the empty interval later, but for now this method just returns 0 when the conjunction of two sets is empty."""
        # It would be nice if there were an easy way to compare endpoints. Then all this mess could be reduced to
        # one line: return Interval(max(self.left, other.left), min(self.right, other.right). I guess it would be overkill to make
        # an endpoint class just for that though. 
        
        if self.start > other.start:
            left = self.start, self.inclusive_start
        elif other.start > self.start:
            left = other.start, other.inclusive_start
        else:
            left = self.start, min(self.inclusive_start, other.inclusive_start)
            
        if self.end < other.end:
            right = self.end, self.inclusive_end
        elif other.end < self.end:
            right = other.end, other.inclusive_end
        else:
            right = self.end, min(self.inclusive_end, other.inclusive_end)
            
        return Interval(left[0], right[0], left[1], right[1])
    
    def union(self, other):
        """This is a weaker form of union, suited to the basic Interval class. 
        The precondition for it working is that self and other have a non-empty
        intersection. It will therefore always return a basic Interval"""
        if self.start < other.start:
            left = self.start, self.inclusive_start
        elif other.start < self.start:
            left = other.start, other.inclusive_start
        else:
            left = self.start, max(self.inclusive_start, other.inclusive_start)
            
        if self.end > other.end:
            right = self.end, self.inclusive_end
        elif other.end > self.end:
            right = other.end, other.inclusive_end
        else:
            right = self.end, max(self.inclusive_end, other.inclusive_end)
            
        return Interval(left[0], right[0], left[1], right[1])
    
    
        


class ArithmeticalInterval(Interval):
    def __add__(self, interval):
        pass
    def __sub__(self, interval):
        pass
    def __mul__(self, interval):
        pass
    def __div__(self, interval):
        pass